class Solution {
public:
    vector<vector<int> > subsetsWithDup(vector<int> &S) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function

        sort(S.begin(), S.end());
        vector<int> subset;
        vector<vector<int> > result;
        getSubsets(S, 0, subset, result);
        return result;
    }

    void getSubsets(const vector<int> &S, int startIndex,
                    vector<int> &subset, vector<vector<int> > &result) {
        result.push_back(subset);
        if (startIndex >= S.size()) {
            return;
        }
        for (int i = startIndex; i < S.size(); ) {
            subset.push_back(S[i]);
            getSubsets(S, i + 1, subset, result);
            subset.pop_back();
            int j = i + 1;
            while (j < S.size() && S[i] == S[j]) {
                ++j;
            }
            i = j;
        }
    }
};
